/**
 * 同322
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
    let goods = []
    for (let i = 1; i * i <= n; i++) {
        goods.push(i * i)
    }
    let dp = new Array(n + 1).fill(n + 1);
    dp[0] = 0
    for (let i = 0;i<goods.length;i++){
        for(let j = goods[i];j<=n;j++){
            dp[j] = Math.min(dp[j],1+dp[j-goods[i]])
        }
    }
    return dp[n] === n+1?0:dp[n]
};